树形动规 :[stupid]愚蠢的矿工 【原型是 选课】 pascal 找错

来源:百度知道 编辑:UC知道 时间:2024/06/28 15:47:54
描述
这个宝藏的制造者为了掩盖世人耳目,他做的宝藏是没有出口,只有入口,不少建造宝藏的人都死在里面.现在知道宝藏总共有N个分岔口,在分岔口处是有财宝的,每个宝藏点都有一个财富值.狗狗只带了M个人来,而且为了安全起见,在每个分岔口,必须至少留一个人下来,这个留下来的人可以挖宝藏(每个人只能挖一个地方的宝藏),这样才能保证不会迷路,而且这个迷宫有个特点,任意两点间有且只有一条路可通.狗狗为了让他的00开心,决定要尽可能地多挖些宝藏回去.现在狗狗的圈叉电脑不在身旁,只能求救于你了,你要知道,狗狗的终身幸福就在你手上了..(狗狗ps:00,你不能就这样抛弃偶……)
输入格式
第1行:两个正整数N,M .N表示宝藏点的个数,M表示狗狗带去的人数(那是一条懒狗,他自己可不做事)。(n<=1000,m<=100)
第2行:N个整数,第i个整数表示第i个宝藏的财富值.(保证|wi|<maxint)
第N+2行:两个非负整数A和B,表示A通向B,当A=0,表示A是入口.(保证A,B<=n)
输出格式
输出狗狗能带回去的宝藏的价值。
样例输入
4 3
5 6 2 4
1 2
0 1
2 3
3 4
样例输出
13
我 的 代码 有点长.. 但是我 觉得和 【选课】 很像...:
program kuanggong;
var a,l,r,f:array[0..1050]of longint;
b:array[-1..1050,-1..150]of longint;
i,j,k,m,n,z,x,y,v,u,s,t:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
procedure init;
begin

这是我的写法
program xy;
var n,m,i,j,k,s:integer;
g:array[0..1000,0..1000]of integer;
a:array[1..1000]of integer;
begin
readln(n,m);
for i:=1 to n do
read(a[i]);
readln;
for i:=0 to n do
for j:=0 to n do
g[i,j]:=maxint;
for k:=1 to n do
begin
readln(i,j);
g[i,j]:=0;
end;
for i:=1 to n do
if g[0,i]=0 then begin s:=s+a[i];k:=i;end;
for i:=2 to m do
begin
j:=1;
while g[k,j]<>0 do j:=j+1;
s:=s+a[j];
k:=j;
end;
write(s);
readln;
end.